﻿#include "Struct.h"

//1.图的创建
mgraph initgraph() {
    mgraph c;
    FILE* f;

    // 尝试打开文件
    f = fopen("map.txt", "r");
    if (f == NULL) {
        perror("无法打开文件map.txt");
        c.vexnum = 0;
        c.arcnum = 0;
        return c;
    }

    // 读取顶点个数和边个数
    if (fscanf(f, "%d %d", &c.vexnum, &c.arcnum) != 2) {
        perror("读取顶点个数和边个数失败");
        fclose(f);

    }

    // 检查顶点个数和边个数合法性
    if (c.vexnum <= 0 || c.vexnum > 100 || c.arcnum < 0 || c.arcnum >(c.vexnum * (c.vexnum - 1) / 2)) {
        perror("顶点个数或边个数数据不合理");
        fclose(f);

    }

    // 读取顶点信息
    for (int i = 1; i <= c.vexnum; i++) {
        if (fscanf(f, "%d", &c.vexs[i].position) != 1) {
            perror("读取顶点位置信息失败");
            fclose(f);

        }
        // 清除换行符或空格
        int ch;
        while ((ch = fgetc(f)) != '\n' && ch != EOF);

        if (fgets(c.vexs[i].name, sizeof(c.vexs[i].name), f) == NULL) {
            perror("读取顶点名称失败");
            fclose(f);

        }
        c.vexs[i].name[strcspn(c.vexs[i].name, "\n")] = '\0';  // 去掉换行符

        if (fgets(c.vexs[i].introduction, sizeof(c.vexs[i].introduction), f) == NULL) {
            perror("读取顶点简介失败");
            fclose(f);

        }
        c.vexs[i].introduction[strcspn(c.vexs[i].introduction, "\n")] = '\0';
    }

    // 初始化邻接矩阵
    for (int i = 1; i <= c.vexnum; i++) {
        for (int j = 1; j <= c.vexnum; j++) {
            c.arcs[i][j].adj = Infinity;
            c.arcs[1][2].adj = 100; c.arcs[2][10].adj = 250; c.arcs[2][3].adj = 200; c.arcs[3][10].adj = 150; c.arcs[4][5].adj = 250;
            c.arcs[4][6].adj = 150; c.arcs[4][11].adj = 150; c.arcs[4][3].adj = 450; c.arcs[5][12].adj = 300; c.arcs[6][13].adj = 175;
            c.arcs[7][13].adj = 200; c.arcs[8][9].adj = 150; c.arcs[8][14].adj = 200; c.arcs[9][11].adj = 150; c.arcs[9][14].adj = 500; c.arcs[10][12].adj = 100;
        }
    }
    for (int i = 1; i <= c.vexnum; i++) {
        for (int j = 1; j <= c.vexnum; j++) {
            c.arcs[j][i].adj = c.arcs[i][j].adj;
        }
    }
    fclose(f);
    return c;
}
//2.查找景点在图中的序号
int locatevex(mgraph c, int v) {
    int i;
    for (i = 1; i <= c.vexnum; i++)
        if (v == c.vexs[i].position) return i; // 找到，返回顶点序号i
    return -1; // 没有找到这个顶点
}
//3.查找并输出序号为m,n景点间的路径
void path(mgraph c, int m, int n, int k) {
    int s, t = k + 1, length = 0; // t用于存放路径上下一个顶点对应的d[]数组元素的下标
    if (d[k] == n && k < 8) { // 若d[k]是终点n且景点个数<=8,则输出该路径
        for (s = 0; s < k; s++) { // 计算路径长度
            length = length + c.arcs[d[s]][d[s + 1]].adj;
        }
        if (length <= 1000) { // 打印路径长度小于定长的路径
            for (s = 0; s < k; s++) { // 输出该路径。s=0时为起点m
                printf("%d%s--->", d[s], c.vexs[d[s]].name);
            }
            printf("%d%s  ", d[k], c.vexs[d[k]].name); // 输出最后一个景点名（即顶点n的名字，此时s==k）
            printf("总路线长为%d米\n\n", length);
        }
    }
    else {
        s = 1;
        while (s <= c.vexnum) { // 从第m个顶点，试探所有顶点是否有路径
            if ((c.arcs[d[k]][s].adj < Infinity) && (visited[s] == 0)) { // 顶点m到顶点s有边(权值不为无穷大)，且未被访问
                visited[s] = 1;
                d[k + 1] = s; // 存储顶点编号
                path(c, m, n, t);
                visited[s] = 0; // 将找到的路径上顶点的访问标志重新设置为0，以用于试探新的路径
            }
            s++; // 试探从下一个顶点s开始是否有到终点的路径
        }
    }
}
//4.查找两景点间的景点的所有路径
int allpath(mgraph c) {
    int k, i, j, m, n;
    printf("\n\n请输入您想要查询的两个景点的编号：\n\n");
    scanf("%d%d", &i, &j); printf("\n\n");
    m = locatevex(c, i); // locatevex确定该顶点是否存在。若存在，返回该顶点编号。
    n = locatevex(c, j);
    d[0] = m; // 存储路径起点m（int d[]数组是全局变量）
    for (k = 0; k < key; k++) // 全部顶点访问标志初值设为0
        visited[k] = 0;
    visited[m] = 1; // 第m个顶点访问标志设置为1
    path(c, m, n, 0); // 调用程序。k=1，对应起点d[1]==m。k为d[]数组下标
    return 1;
}
//5.用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径
void shortestpath_dij(mgraph c) {
    int v0, v, w, k = 1, min, t, p;
    int final[MaxVertexNum]; // final[w]=1表示已经求得顶点V0到Vw的最短路径
    int Patharc[MaxVertexNum]; // 用于存储最短路径下标的数组
    int ShortPathtable[MaxVertexNum]; // 用于存储到各点最短路径的权值和

    printf("\n请输入一个起始景点的编号：");
    scanf("%d", &v0); printf("\n\n");
    while (v0 < 0 || v0 > key) {
        printf("\n您输入的景点编号不存在\n");
        printf("请重新输入：");
        scanf("%d", &v0);
    }

    // 初始化数据
    for (v = 1; v <= c.vexnum; v++) { // 数组0还是空出来
        final[v] = 0; // 全部顶点初始化为未找到最短路径
        ShortPathtable[v] = c.arcs[v0][v].adj; // 将与v0点有连线的顶点加上权值
        Patharc[v] = 0; // 初始化路径数组p为0
    }
    ShortPathtable[v0] = 0; // V0至v0的路径为0
    final[v0] = 1; // V0至v0不需要路径

    // 开始主循环，每次求得V0到某个v顶点的最短路径
    for (v = 1; v <= c.vexnum; v++) {
        min = Infinity;
        for (w = 1; w <= c.vexnum; w++) { // 找出最近的顶点和权值
            if (!final[w] && ShortPathtable[w] < min) { // 有边
                k = w;
                min = ShortPathtable[w];
            }
        }
        final[k] = 1; // 将目前找到的最近的顶点置1
        // 修正当前最短路径及距离
        for (w = 1; w <= c.vexnum; w++) {
            // 如果经过v顶点的路径比现在这条路径的长度短的话，更新
            if (!final[w] && (min + c.arcs[k][w].adj < ShortPathtable[w])) {
                ShortPathtable[w] = min + c.arcs[k][w].adj; // 修改当前路径长度
                Patharc[w] = k; // 存放前驱结点
            }
        }
    }

    // 打印最短路径
    for (t = 1; t <= c.vexnum; t++) {
        p = t;
        if (t != v0) { 
            printf("%d%s", t, c.vexs[t].name);
            for (w = 1; w <= c.vexnum; w++) {
                if (Patharc[p] != 0) {
                    printf("<--%d%s", Patharc[p], c.vexs[Patharc[p]].name);
                    p = Patharc[p];
                }
            }
            printf("<--%d%s", v0, c.vexs[v0].name);
            printf("\n总路线长为%d米\n\n", ShortPathtable[t]);
        }
    }
}
//6.菜单
void menu() {
    printf(" *****************欢迎使用高校导航系统********************\n");
    printf(" │                    四川轻化工大学                     │\n");
    printf(" │                     菜 单 选 择                       │\n");
    printf(" │    1.返回菜单              2.景点信息查询             │\n");
    printf(" │    3.查询景点间最短路径     4.查询景点间所有路径      │\n");
    printf(" │    5.查看游览路线           6.修改一个已有景点        │\n");
    printf(" │    7.增加一个新景点         8.增加一条新的路径        │\n");
    printf(" │    9.删除一个景点           10.删除一条路径           │\n");
    printf(" │    0.退出                                             │\n");
    printf(" *********************************************************\n");
}
//7.更新图的部分信息
int newgraph(mgraph* c) {
    int changenum;
    int i, m, n, t, distance, v0, v1;
    printf("\n下面请输入您要修改的景点的个数：\n");
    scanf("%d", &changenum);
    while (changenum < 0 || changenum > key) {
        printf("\n输入错误！请重新输入");
        scanf("%d", &changenum);
    }
    for (i = 0; i < changenum; i++) {
        printf("\n请输入景点的编号：");
        scanf("%d", &m);
        t = locatevex(*c, m);
        printf("\n请输入修改后景点的名称:");
        scanf("%s", &c->vexs[t].name);
        printf("\n请输入修改后景点的简介:");
        scanf("%s", &c->vexs[t].introduction);
    }
    printf("\n下面请输入您要更新的边数");
    scanf("%d", &changenum);
    while (changenum < 0 || changenum > key) {
        printf("\n输入错误！请重新输入");
        scanf("%d", &changenum);
    }
    if (changenum != 0)
        printf("\n下面请输入更新边的信息：\n");
    for (i = 1; i <= changenum; i++) {
        printf("\n修改的第%d条边的起点 终点 长度为：", i);
        scanf("%d %d %d", &v0, &v1, &distance);
        m = locatevex(*c, v0);
        n = locatevex(*c, v1);
        if (m >= 0 && n >= 0) {
            c->arcs[m][n].adj = distance;
            c->arcs[n][m].adj = c->arcs[m][n].adj;
        }
    }
    return 1;
}
//8.增加一条边
int enarc(mgraph* c) {
    int m, n, distance;
    printf("\n请输入边的起点和终点编号，权值：");
    scanf("%d %d %d", &m, &n, &distance);
    while (m < 0 || m > c->vexnum || n < 0 || n > c->vexnum) {
        printf("输入错误，请重新输入：");
        scanf("%d %d", &m, &n);
    }
    if (locatevex(*c, m) < 0) {
        printf("此节点%d已删除", m);
        return 1;
    }
    if (locatevex(*c, n) < 0) {
        printf("此节点%d已被删除", n);
        return 1;
    }

    c->arcs[m][n].adj = distance;
    c->arcs[n][m].adj = c->arcs[m][n].adj;
    c->arcnum++;
    return 1;
}
//9.增加一个结点。
int envex(mgraph* c)
{
    int i;
    c->vexnum++;//顶点个数+1
    printf("请输入您要增加结点的信息：");
    printf("\n编号：");
    scanf("%d", &c->vexs[c->vexnum].position);
    printf("名称：");
    scanf("%s", &c->vexs[c->vexnum].name);
    printf("简介：");
    scanf("%s", &c->vexs[c->vexnum].introduction);

    for (i = 1; i <= c->vexnum; i++)
    {
        c->arcs[c->vexnum][i].adj = Infinity;
        c->arcs[i][c->vexnum].adj = Infinity;
    }
    return 1;
}
//10.删除图的一个顶点。
int delvex(mgraph* c)
{
    int i = 0, j;
    int m, v;
    if (c->vexnum <= 0)
    {
        printf("图中已无顶点");
        return 1;
    }
    printf("\n下面请输入您要删除的景点编号：");
    scanf("%d", &v);
    while (v<0 || v>key)
    {
        printf("\n输入错误！请重新输入:");
        scanf("%d", &v);
    }
    m = locatevex(campus, v);
    if (m < 0)
    {
        printf("此顶点%d已删除\n", v);
        return 1;
    }
    for (i = m; i <= c->vexnum - 1; i++)
        for (j = 1; j <= c->vexnum; j++)//将二维数组中的第m+1行依次向前移动一行（删除第m行） 
            c->arcs[i][j] = c->arcs[i + 1][j];
    for (i = m; i <= c->vexnum - 1; i++)
        for (j = 1; j <= c->vexnum; j++)//将二维数组中的第m+1列依次向前移动一列（删除第m列）
            c->arcs[j][i] = c->arcs[j][i + 1];
    c->vexs[v].position = -1;//表示此点已删除，后期打印也不会显示该点 
    c->vexnum--;//顶点个数-1 
    return 1;
}
//11.删除图的一条边。
int delarc(mgraph* c)
{
    int m, n, v0, v1;
    if (c->vexnum <= 0)
    {
        printf("图中已无边，无法删除。");
        return 1;
    }
    printf("\n下面请输入您要删除的边的起点和终点编号：");
    scanf("%d %d", &v0, &v1);
    m = locatevex(campus, v0);
    if (m < 0)
    {
        printf("此%d顶点已删除", v0);
        return 1;
    }
    n = locatevex(campus, v1);
    if (n < 0)
    {
        printf("此%d顶点已删除", v1);
        return 1;
    }
    c->arcs[m][n].adj = Infinity;//将删掉的边的权值改为无穷 
    c->arcs[n][m].adj = Infinity;
    c->arcnum--;//图中边数减1 
    return 1;
}
//12.查询两景点间的最短路径
void floyd(mgraph c)
{
    int i, j, k;
    for (i = 1; i <= key; i++)//将图的邻接矩阵赋值给 shortest二维数组，将矩阵pathh全部初始化为-1 
    {
        for (j = 1; j <= key; j++)
        {
            shortest[i][j] = c.arcs[i][j].adj;
            pathh[i][j] = j;
        }
    }

    for (k = 1; k <= key; k++)//核心操作，完成了以k为中间点对所有的顶点对（i,j）进行检测和修改 
    {
        for (i = 1; i <= key; i++)
        {
            for (j = 1; j <= key; j++)
            {
                if (shortest[i][j] > shortest[i][k] + shortest[k][j])
                {
                    shortest[i][j] = shortest[i][k] + shortest[k][j];
                    pathh[i][j] = pathh[i][k];//记录一下所走的路 //P数组用来存放前驱顶点  
                }
            }
        }
    }
}
//13.任意两点间最短距离
void display(mgraph c, int i, int j)
{
    int a, b;
    a = i; b = j;
    printf("您要查询的两景点间最短路径：\n\n");
    printf("%d%s", a, c.vexs[a].name);
    while (pathh[i][j] != b)
    {
        printf("-->%d%s", pathh[i][j], c.vexs[pathh[i][j]].name);
        i = pathh[i][j];
    }
    printf("-->%d%s\n\n", b, c.vexs[b].name);
    printf("%s-->%s的最短路径是：%d 米。\n\n", c.vexs[a].name, c.vexs[b].name, shortest[a][b]);
}
//14.查询景点的信息
int shortdistance(mgraph c)
{
    int i, j;
    printf("请输入要查询的两个景点的数字编号（1->11）中间用空格间隔开。\n");
    scanf("%d %d", &i, &j);
    if (i > key || i<0 || j>key || j < 0)
    {
        printf("输入信息错误！\n\n");
        printf("请输入要查询的两个景点的数字编号（1->11）中间用空格间隔开。\n");
        scanf("%d %d", &i, &j);
    }
    else
    {
        floyd(c);
        display(c, i, j);
    }
    return 1;
}
//15.显示所有景点信息
void browsecompus(mgraph c)
{
    int i;
    printf(" \n\n编号        景点名称                   简介\n");
    printf("____________________________________________________________________________________________\n");
    for (i = 1; i <= c.vexnum; i++)
    {
        if (c.vexs[i].position != -1)
            printf("%-10d%-25s%-80s\n", c.vexs[i].position, c.vexs[i].name, c.vexs[i].introduction);
    }
    printf("____________________________________________________________________________________________\n");
}